import java.util.ArrayList;
import java.util.List;

public class KMP {
    /**
     * 判断主串中是否含有子串
     * @param str 主串
     * @param target 子串
     * @return 若主串中含有子串，返回主串中子串第一次出现的起始下标；若不含有，返回 -1
     */
    public int KMP(String str, String target) {
        // 处理特殊情况
        if (str == null || target == null) {
            return -1;
        }
        int strLen = str.length();
        int targetLen = target.length();
        if (strLen == 0 || targetLen > strLen) {
            return -1;
        }
        // 求 next 数组
        int[] next = new int[targetLen];
        getNext(next, target);
        // 开始判断
        int i = 0, j = 0;
        while (i < strLen && j < targetLen) {
            // 判断 str 中 i 位置字符是否与 target 中j 位置字符相同
            // 不要忘记处理 j = -1 的情况
            if (j == -1 || str.charAt(i) == target.charAt(j)) {
                // 相同，i 和 j 都向后移动
                i++;
                j++;
            } else {
                // 不相同，j 进行回退
                j = next[j];
            }
        }
        // 子串先遍历完
        if (j >= targetLen) {
            return i - j;
        } else {
            // 主串先遍历完
            return -1;
        }
    }

    /**
     * 求 j 位置匹配失败时，应该回退的下标位置
     * @param next 存在 j 应该回退的位置
     * @param target 子串
     */
    private void getNext(int[] next, String target) {
        // 处理特殊情况
        if (target == null) {
            return;
        }
        int len = next.length;
        if (len == 0) {
            return;
        }
        next[0] = -1;
        // 若子串中只有一个字符，直接返回
        if (len == 1) {
            return;
        }
        next[1] = 0;
        int j = 1, k = 0;
        // 遍历子串，依次求 j + 1 位置的回退下标
        while (j < len - 1) {
            // 当 k 为 -1 或 j 位置字符与 k 位置字符相同时，next[j + 1] = k + 1
            // 不要忘记处理 k = -1 的情况
            if (k == -1 || target.charAt(j) == target.charAt(k)) {
                next[j + 1] = k + 1;
                // 更新 j 和 k 的值
                j++;
                k++;
            } else {
                // 继续回退
                k = next[k];
            }
        }
    }

    /**
     * 优化
     * @param nextval
     * @param target
     */
    private void getNextval(int[] nextval, String target) {
        // 处理特殊情况
        if (target == null) {
            return;
        }
        int len = nextval.length;
        // 若没有元素，则直接返回
        if (len == 0) {
            return;
        }
        nextval[0] = -1;
        // 初始化 j 和 k 的值
        int j = 0, k = -1;
        // 遍历子串，依次求 j + 1 位置的回退下标
        while (j < len - 1) {
            if (k == -1 || target.charAt(j) == target.charAt(k)) {
                // 更新 j 和 k 的值
                j++;
                k++;
                // 将 j 回退到最终位置
                if (j != target.length() && target.charAt(j) == target.charAt(k)) {
                    nextval[j] = nextval[k];
                } else {
                    // j 位于 len 位置，或 j 位置元素不等于 k 位置元素，j 最终回退到 k 位置
                    nextval[j] = k;
                }
                // nextval[j] = target.charAt(j) != target.charAt(k) ? k : nextval[k];
            } else {
                // 继续回退
                k = nextval[k];
            }
        }
    }

    /**
     * 查找所有起始位置
     * @param str 主串
     * @param target 子串
     * @return 查询结果集
     */
    public List<Integer> findAll(String str, String target) {
        List<Integer> ret = new ArrayList<>();
        // 处理特殊情况
        if (str == null || target == null) {
            return ret;
        }
        int strLen = str.length();
        int targetLen = target.length();
        if (strLen == 0 || targetLen > strLen) {
            return ret;
        }
        // 求 next 数组(计算 targetLen + 1) 位
        int[] next = new int[targetLen + 1];
        getNext(next, target);
        // 开始判断
        int i = 0, j = 0;
        while (i < strLen) {
            // 判断 str 中 i 位置字符是否与 target 中 j 位置字符相同
            // 不要忘记处理 j = -1 的情况
            if (j == -1 || str.charAt(i) == target.charAt(j)) {
                // 相同，i 和 j 都向后移动
                i++;
                j++;
                // 判断是否已经匹配成功
                if (j == targetLen) {
                    ret.add(i - j);
                    j = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        KMP kmp = new KMP();
        System.out.println(kmp.findAll("aaaaaa", "aaaa"));
    }

}
